Ｄｆｔ計算用装置

专利摘要:
例えばＧＮＳＳ受信器中で、ＤＦＴ計算を行なうための装置であって、一定の整数値による乗算器の２つのバンクを含んでいる。この整数値はＤＦＴ中の回転因子の実数部および虚数部を表わしている。制御装置は、適切な乗算器を通して選択的にデータをルーティングして所望のＤＦＴ項を得る。使用されていない乗算器は、動的な電力を最小化するために一定の入力値に固定される。
公开号:JP2011511352A
申请号:JP2010544596
申请日:2008-05-15
公开日:2011-04-07
发明作者:センシオッティ、アンドレア；バリオラ、ネスター・ルカス；ヤング、フィル
申请人:クゥアルコム・インコーポレイテッドＱｕａｌｃｏｍｍ Ｉｎｃｏｒｐｏｒａｔｅｄ；
IPC主号:G06F17-14

专利说明:

[0001] 本発明は、特に（しかし排他的ではない）全地球航法衛星システム（ＧＮＳＳ）用受信器への組込みに適合されたＤＦＴ（離散フーリエ変換）プロセッサに関する。本発明の実施形態は、１つのＤＦＴラインを選択的に活性化することに基づいて電力および面積を最適化されたアーキテクチャに関する。]
背景技術

[0002] フーリエ変換（ＦＴ）は、信号を時間領域から周波数領域に変換する関数である。有限期間の離散的信号｛ｘ０，…，ｘＮ−１｝の場合、フーリエ変換は、大抵、離散フーリエ変換（ＤＦＴ）と称される。]
[0003] フーリエ変換は、その他の多くの適用形態もあるが、ＧＰＳ、Ｇａｌｉｌｅｏ、ＧＬＯＮＡＳＳ、および他のＧＮＳＳ信号の復調および処理において適用される。これらの適用形態では、被受信データ（受信されたデータ、received data）に適用されるフーリエ変換は、複数のキャリア（搬送波）周波数を並列に処理することを可能にし、重要なことにハードウェアの複雑さを減ずる。現代のＧＮＳＳ受信器またはプロセッサは「ＤＦＴエンジン」（これはＤＦＴの計算に特に専用の部分である）をほとんどの場合含んでいる。]
[0004] ＦＴベースのＧＮＳＳ信号処理の理論および詳細は当技術分野において知られており、本明細書において詳細に詳述されない。網羅的な情報は、利用可能な文献、例えばE. D: KaplanおよびC. Hegarty編集、London、Artech House出版（ ２００５年１２月）の書籍「Understanding GPS and its applications」第２版、において知ることが可能である。]
[0005] 言及されている有限のサンプル化された信号｛ｘＮ｝についてのＤＦＴ点Ｘｋの定義は次の通りである。]
[0006] ＤＦＴを計算するための効率的なアルゴリズムは、分割に基づいた有名な高速フーリエ変換（ＦＦＴ）であり、アプローチを克服する。Ｎ（２の累乗）個のサンプル・データ・ストリームが、半分にされるとともに並列処理される場合、計算次数（order）はＮ２／２回の複素の加算および（Ｎ２／２＋Ｎ）回の複素の乗算へと低減される。可能な分割の数がｌｏｇ２（Ｎ）であるので、計算次数は、Ｎ・ｌｏｇ２（Ｎ）回の複素の加算およびＮ・ｌｏｇ２（Ｎ）／２回の複素の乗算によって与えられることになる。]
[0007] ＦＦＴアルゴリズムを使用することは、概して、Ｎ個のＤＦＴ点をＮ個のサンプルから計算する最も効率的な方法と考えられている。しかしながら、ＦＦＴアルゴリズムが最適でないＤＦＴ構成がある。例えば、Ｍ（Ｍ≦Ｎ）個のＤＦＴラインの縮小された組だけが必要な適用形態（信号処理において、および特にＧＮＳＳプロセッサにおいて多く見られる）では、ＦＦＴアーキテクチャの計算次数は最適化されない。]
[0008] また、ＦＦＴアルゴリズムは、Ｎが２の累乗である場合のみ、最も単純で最も効率的な形態を取る。任意のＮ用の様々なＦＦＴアルゴリズムが存在するが、それらは一般にそれほど効率的でない
ＧＮＳＳ信号プロセッサでは、ＤＦＴ計算は、受信器のコスト、シリコン面積、および電力消費に直接反映する。したがって、できるだけ低い演算負荷を有するＤＦＴアルゴリズムを提供する要求がある。]
[0009] フーリエ変換はサイン関数とコサイン関数の正規直交基底にわたって時間領域中の関数をスペクトル分解することと見なされることが可能である。他の多くの離散積分変換が、信号処理技術において関連し、相違する正規直交基底に対応する。これらの変換は、例えば、コサイン変換（ＤＣＴ）およびその様々な改良版（ＭＤＣＴ）、離散ハートレー変換（ＤＨＴ）、および他の多くのものを含んでいる。明細書の前述の部分は、簡略化のため、ＤＦＴ変換のみに言及している。しかしながら、本発明がこの具体的な事例に制限されず、それが適用される離散積分変換を全て含んでいることが理解されなければならない。]
[0010] 本発明の目的は、ＧＮＳＳ信号処理用の信号プロセッサ中でＤＦＴラインの組を計算するためのより効率的なアルゴリズムを提供することである。また、本発明は、低出力のＧＮＳＳ受信器を提供することを目的とする。]
[0011] 本発明の目的は添付の独立形式の請求項、重要ではあるが厳密に本質的ではない要素を取り入れている従属クレームの変形体によって達成される。本発明は、いくつかの実施形態の詳細な記述および概略的に例示する図面を参照することにより、一層よく理解されるだろう。実施形態は、例のみとして提供されている。]
図面の簡単な説明

[0012] ＤＦＴコンピューティングの既知の実現形態。
図１の既知の装置のパイプライン版変形体。
本発明の一側面によるＤＦＴエンジンの構造。
図３の構造で使用しているハーフ・バタフライ・アーキテクチャ。
（Ｋ＋１）／２個の定数乗算器モジュールを伴った、偶数係数バンクの詳細。
（Ｋ＋１）／２個の定数乗算器モジュールを伴った、奇数係数バンクの詳細。
ＧＮＳＳ衛星捕捉中の探索空間を表現する図。
ＧＮＳＳ受信器アーキテクチャ。
具体的な事例における、複素平面中のＤＦＴの回転因子の位置。] 図１ 図３
実施例

[0013] 本発明は、ＧＮＳＳ処理が概して限られた数のＤＦＴラインの計算を必要とするという観察に基づいている。ＧＮＳＳＤＦＴエンジン中で使用される回転因子は有限集合であり、また、それらの実数部および虚数部において特別の対称性を有している。したがって、本発明は、Ｎが必ずしも２の累乗でないＮ個のサンプルのうちのＤＦＴラインの縮小された組Ｍ（Ｍ≦Ｎ）を計算することが可能な最適化されたＤＦＴアルゴリズムを提案する。このことは、これらの対称性を利用している。]
[0014] これらの目的のための、データ形式の検討、使用されていないＤＦＴラインの動的な無効化、およびルーティングが効率的なデザイン区分化が、考慮されねばならない。]
[0015] 直接的なＤＦＴ実現形態は、図１に例示されているように、等式（４）の実数部および虚数部を計算するのに必要な４つの乗算器および２つの加算器に基づいている。これは、通常、完全バタフライ回路またはアルゴリズムと称される。係数ＣＩ、ＣＱは、例えば予め計算された表（図示せず）から取り出されることが可能である。] 図１
[0016] 図２は、完全バタフライ回路の変形体、すなわちハーフ・バタフライを示している。これは、パイプラインアプローチを採用している。マルチプレクサ２０１およびデマルチプレクサ２０６が使用されて、２つ乗算器２０２、２０３、および１つの加算器２０４のみを有する演算ブロック２０５中で実数部２０７および虚数部２０８を別々に計算する。その結果は複素レジスタ２０９に格納される。] 図２
[0017] ここで、Ｔｓはサンプル期間であり、ＮはＤＦＴのための入力信号の長さ（点の数によって表現されている）であり、Ｍ（Ｍ≦Ｎ）は計算されるＤＦＴラインの数であり、Ｎｅｆｆは実効的なＤＦＴ長さ（いくつの点が実際に積分されるか）である。]
[0018] 相違する係数の数Ｋは、ＤＦＴ点の数Ｎに依存する。Ｎが８の整数倍であるとして、ｎ次の複素数の１の累乗根の対称性を活用すると、相違する係数の数ＫはＮ／４＋１である。この公式は、Ｎ＝８、１６、２４、３２、４０、４８について、Ｋ＝３、５、７、９、１１、１５を与える。これを、Ｎの他の値をサポートするＤＦＴエンジン、またはＫの値の任意の有限の選択まで拡大することは簡単である。例えば、Ｎが値｛８，１６，２４，３２｝の範囲内で設定可能であることが意図されている場合、必要な係数の数Ｋは、（Ｋ（２４）＋Ｋ（３２）−Ｋｃ）である。ここで、Ｋｃは、Ｎ＝２４〜Ｎ＝３２（複素偏角０°または４５°を有するもの）の共通な係数の数である。]
[0019] 次に、本発明の実施形態が図３を参照して記述される。バタフライ演算ブロック２０５の半分は、図２中で同じ符合によって示されているブロックと機能的に同じである。しかしながら、以下に説明されるように、その構造は異なる。] 図２ 図３
[0020] 制御ロジックユニット３０３は、ＤＦＴエンジンの演算を駆動する。これは、入来する構成パラメータ３０１を利用して、入力バッファ３０２から、処理されるデータ２０１を選択する。構成パラメータ３０１およびバッファ３０２中の入力データは様々な供給源を有することが可能である。ＧＮＳＳ受信器の場合は、例えば、構成を図示されていないＣＰＵによって提供され得、また入力データが相関ユニットによって生成されることが可能である。しかしながら、他の構成が可能である。制御ロジックユニット３０３はまた、現在の係数ペア３０４の選択を制御し、等式（４）の実数部または虚数部が処理されているかに応じて、部分項がハーフ・バタフライ・ユニット２０５において加えられるべきか減じられるべきかを判断する。]
[0021] ハーフ・バタフライ２０５はまず実数部２０７（Ｉ・ＣＩ−Ｑ・ＣＱ）を計算し、デマルチプレクサ２０６は結果を複素結果レジスタ２０９のＩ部分に駆動する。次に、ハーフ・バタフライは虚数部２０８（Ｉ・ＣＱ−Ｑ・ＣＩ）を計算し、結果を複素結果レジスタ２０９のＱ部分において格納する。]
[0022] 複素結果２０９は、随意的にスケーリング・ユニット３０５によって一定の係数を乗じられ、加算器３０６およびメモリ３０８（例えばＲＡＭ）を具備するアキュムレータにおいて先のＤＦＴ項と累算される。]
[0023] 本発明のＤＦＴは、累算ＲＡＭ３０８におけるオーバーフローを検出するために飽和段階３０７を含むことが好ましい。飽和が起こった場合、フラグ３１０が有効にされる。ＤＦＴ制御ロジック３０３または外部の制御ユニットは、飽和を回避するために、適切なスケーリング係数を計算するためのアルゴリズムを実行する。]
[0024] 本発明のＤＦＴ処理装置は、構成パラメータ３０１によって示される、任意の使用されていないＤＦＴラインを動的に無効化するように構成されることが好ましい。入力データセレクタ２０１は「０」に固定されることが可能で、切り捨てられたＤＦＴラインのためのハーフ・バタフライ２０５およびスケーラ３０５の切替え（toggling）を減じる。さらに、制御ロジック３０３は、ＲＡＭ３０８のアドレスは更新するが、不要かつ電力浪費するメモリリード／ライトアクセスを回避するために使用されることが可能である。]
[0025] 本発明の好ましい変形体によれば、ＤＦＴプロセッサは、図４に例示される構造を有するハーフ・バタフライ２０５を含んでいる。これは２つのステップで等式（４）を計算する。まず、実数部（Ｉ・ＣＩ−Ｑ・ＣＱ）が計算され、次に虚数部（Ｉ・ＣＱ−Ｑ・ＣＩ）が計算される。] 図４
[0026] 図４の構造は、４５°の複素偏角倍数を有する係数Ｃ４５を唯一の例外として常にＣｉ≠Ｃｑであるという事実、および係数の組が偶数の一定の係数｛Ｃ０，Ｃ２，…，Ｃｋ−１｝および奇数の一定の係数｛Ｃ１，Ｃ３，…，Ｃｋ−２｝の２つの別個のグループへ分割されることが可能であるという事実を利用している。下位分割（subdivision）は、同一グループについて２つの係数がハーフ・バタフライ項を計算するために必要であることが決して起こらないように行なわれる。ブロック４０３は、一定の偶数の係数｛Ｃ０，Ｃ２，…，Ｃｋ−１｝のうちの１つによって乗じるように具体的に構成されている複数の乗算器を含んでおり、他方、ブロック４０６は、一定の奇数の係数｛Ｃ１，Ｃ３，…，Ｃｋ−２｝のうちの１つによって乗じるように具体的に構成されている複数の乗算器を含んでいる。いずれのブロックもＣ４５係数による乗算器を含んでいる。] 図４
[0027] 再び図４を参照すると、入力サンプルＩ、ＱおよびＫ係数は、符号・絶対値として符号化されることが好ましい。入来データが符号・絶対値フォーマットでない場合、結局、面積の点で小さなオーバーヘッドで、さらなる変換ロジックがＩおよびＱデータの前に加えられることが可能である。ブロック４０３および４０６においてデータの絶対値および選択された係数の絶対値が乗じられて積の絶対値を得る。乗算器が絶対値を扱わねばならないという事実により、内部切替えおよび動的な電力消費は、２の補数フォーマットによる数を経るように構成されている従来の乗算器に比べて、非常に少ない。] 図４
[0028] バンク４０３および４０６に含まれている、定数値による乗算器は、整数演算において実行され、高度に最適化されることが好ましい。０°または９０°の複素偏角を有する重要でない係数は、面積と電力をさらに最小化するためにシフトおよび切捨て演算として実現される。適切であれば、いくつかの係数は、構造を簡素化するとともに乗算器の電力消費を削減するために、わずかに理論値に外れていてもよい。]
[0029] 示されている例において、ハーフ・バタフライの出力は２の補数フォーマットにある。４０３および４０６において計算された積が符号・絶対値フォーマットで符号化されているので、変換ブロック４０９は、データが加算器４１０によって組み合わせられる前に、必要な変換を行なう。構成ポート４０７は、ハーフ・バタフライが複素ＤＦＴ結果２０９の実数部（Ｉ・ＣＩ−Ｑ・ＣＱ）を計算しているか虚数部（Ｉ・ＣＱ−Ｑ・ＣＩ）を計算しているかを選択する。また、データを２の補数フォーマットに変換する前にデータの符号および係数の符号を知ることが必要である。出力の符号・絶対値符号化を得るために、変換ブロック４０９を迂回することも可能である。加算器４１０の出力は、等式（４）の１つのＤＦＴの実数部または虚数部である。変形体によれば、値Ｉ、Ｑは符号の無い整数として表わされ、またバンク４０３および４０６の乗算器は符号無しモードで動作する。別々に計算された結果の符号は、２の補数ユニット４０８および４０９に作用することによって設定される。]
[0030] バンク４０３および４０６に含まれている各定数乗算器モジュールは、制御装置３０３からの構成バス４０２および４０５によって動的に活性化される。それによって、所与の瞬間において、現在のＤＦＴライン計算のために実際に必要な回路の一部のみが活性とされており、大抵の場合、バンク４０３および４０６中の乗算器は不活性な静止状態にある。等式（４）中の項の合算の順序（order）は並べ替えられることが可能である（スクランブリング）。]
[0031] 図５は、偶数の係数バンク４０３についての可能な構造を示している。入力信号５０１は、マルチプレクサ４０１（図４）によって行なわれたＩとＱとの間の選択の結果である。この信号５０１は、（Ｋ＋１）／２個の定数乗算器モジュール５０３全てに共通である。現在のＤＦＴライン計算のために実際に必要な回路の一部だけを活性化する可能性は、４０２からの制御信号を使用して行なわれ、（Ｓｅｌ＿Ｉ＿０，Ｓｅｌ＿Ｑ＿０，…，Ｓｅｌ＿Ｉ＿Ｋ−１，Ｓｅｌ＿Ｑ＿Ｋ−１）として列挙されている。] 図４ 図５
[0032] 同様のアプローチが、奇数の係数バンクについての図６に示されている。入力信号６０１は、マルチプレクサ４０４によって行なわれたＩとＱとの間の選択の結果である。この信号６０１は、４０６中の（Ｋ＋１）／２個の定数乗算器モジュール全てに共通である。現在のＤＦＴライン計算のために実際に必要な回路の一部だけを活性化する可能性は、４０５からの制御信号を使用して行なわれ、（Ｓｅｌ＿Ｉ＿１，Ｓｅｌ＿Ｑ＿１，…、Ｓｅｌ＿Ｉ＿Ｋ−２，Ｓｅｌ＿Ｑ＿Ｋ−２，Ｓｅｌ＿Ｉ＿４５°，Ｓｅｌ＿Ｑ＿４５°）としてまた列挙されている。４５°についての係数を有する乗算ユニット６０５は４０３においても利用可能であるが、４０６において複製されなければならない。４０３からのどの係数が４０６内の６０５としてマークされているかは、採用された係数の符号化に依存する。] 図６
[0033] ２つの係数だけがそのために必要であり、よって、２つの定数乗算器ユニット（各係数バンク４０３および４０６から１つずつ）だけが同時に活性化される。他の定数乗算器ブロックは、自身の入力を０に固定される（組み合わせのロジック切替えによる消費はない）。]
[0034] このアプローチは、標準的な乗算器アプローチと比較して、約３０％の切替え動作を減少させる。また、アーキテクチャは全く組み合わせによるものであり、内部でパイプライン段階は全く存在しない。典型的に、ディジタル回路中のパイプラインは、面積と電力消費の点において最適化されない単純なフリップフロップをベースとするレジスタを使用して実現される。それらを回避することによって、面積および電力が最小化される。]
[0035] 計算されているＤＦＴラインの次数（order）は制御ロジック・ブロック３０３および３０４の内部で管理される。ＤＦＴラインは、ＣＰＵにとっての後処理演算負荷が軽減されるように、プログラム可能な次数（order）で計算されることが可能である。]
[0036] 図５および図６を参照し、ＣＩ＝Ｃ０およびＣＱ＝Ｃ１であるとすると、等式（４）の計算は以下に記述されている２つのステップで行われることが可能である。] 図５ 図６
[0037] ステップ１：等式（４）の実数部の計算：Sel_I_0=1, Sel_Q_1=1, Sel_I_x=0 if x≠0, Sel_Q_x=0 if x≠1, Sel_I=1, Sel_Q=1,DFT_Re=1. Then A=I・C0, B=-Q・C1
ステップ２：等式（４）の虚数部の計算：Sel_I_1=1, Sel_Q_0=1, Sel_I_x=0 if x≠1, Sel_Q_x=0 if x≠0, Sel_I=0, Sel_Q=0, DFT_Re=0. Then D=Q・C0, C=I・C1。]
[0038] ＧＮＳＳ受信器実施形態
ＤＦＴアルゴリズムは、本技術分野中で概して知られており、技術文献において記述されている。下記では、ＧＮＳＳ実現形態に特有の側面だけが図７および図８を参照して詳述される。] 図７ 図８
[0039] 図７を参照すると、ＧＰＳ宇宙船（ＳＶ）の捕捉および追跡は、周波数／符号バイナリ（bin）７０５の決定を必要とする。この目的のための、特定の資源が、符合位相オフセット・ビン７０３およびドップラー・バイナリ７０４を割り出すために必要である。上記の引用されているパラメータのより多くのパラメータのうちの１つの推定がない場合、周波数／符合探索空間全体にわたる全探索が行なわれるべきである。] 図７
[0040] 逐次探索アプローチ（入来するＧＰＳ信号のあり得る全てのドップラーに対する周波数掃引および、ＧＰＳ ＰＲＮ（疑似ランダム信号）符号についての１０２３個の可能な値に対する符合位相掃引が行なわれるアプローチ）は、ＧＮＳＳシステム中の捕捉ステップのために広く用いられている方法である。]
[0041] 並列周波数アプローチは、捕捉プロセスを高速化するために使用され得る。図８に例示されている受信器アーキテクチャは周波数領域で並行探索を行なって、処理されたＧＮＳＳと所与のＳＶについてのＰＲＮの局部生成された複製８０４との間の相関８０５から生成された信号のＤＦＴ８０６を算出する。] 図８
[0042] 参照されている衛星の見通線速度は＋／−１０ｋＨｚオーダーのドップラー効果を生み出す。１５０Ｈｚのステップ周波数ステップが、低レベルのＧＮＳＳ信号のシナリオについて必要な最小値である。]
[0043] 相関された信号８０５の利得は、フォーマットｓｉｎｃ（ｘ）：＝ｓｉｎ（ｘ）・（ｘ）−１を有する。ここで、ｘ＝πｆＴである。このｓｉｎｃ包絡線をＤＦＴ伝達関数に適用すると、全てのＤＦＴラインが、ＰＲＮ符号が完全に一致しているという条件下で中心周波数ラインｆ（これはドップラー周波数に相当する）を例外として振幅損失によって影響されるであろうことが明らかになる。そうでない場合、ピークは存在しない。]
[0044] 前述の特性は、相関器８０５からのＮ個のデータ・サンプルのうちのＤＦＴラインの減じられた個数Ｍを使用することを正当化する。]
[0045] 本発明は、さらに、ハードウェア複雑性および電力消費を減じるためにスペクトル線の減少された個数のためのＤＦＴプロセッサに関係する。]
[0046] ＳＶナビゲーションに特有の適切な設計制約を注意深く適用することおよびＤＦＴアルゴリズムを解析することによって、最適化されたハードウェア・アーキテクチャが、周波数領域の解析をＧＮＳＳチップセットに効率的に埋め込むために実現されることが可能である。]

权利要求:

請求項1
値を、一定の係数の有限集合の中の要素で乗じるための装置であって、複数の乗算器を具備し、各乗算器は前記有限集合の中の前記一定の係数のうちの１つによって乗じるように具体的に構成されている、装置。
請求項2
先行する請求項の装置において、前記値を前記有限集合の中の所望の係数で乗じる乗算器にルーティングするように動作可能に構成されたシーケンス制御ブロックを含む装置。
請求項3
先行する請求項の装置において、前記値および前記係数が複素数値を有する装置。
請求項4
先行する請求項のうちのいずれかの装置が、ＤＦＴまたはＤＣＴまたは離散積分変換を計算するように構成されている装置。
請求項5
ＤＦＴ変換を計算するための装置であって、複数の乗算器回路（５０３）であって、各乗算器回路は入力値をＤＦＴの回転因子の実数部または虚数部に対応する所定の一定の係数（Ｃ０〜Ｃ８）を乗じるように構成されている、複数の乗算器回路を具備し、前記ＤＦＴの回転因子に対応する１対の前記乗算器を活性化するように動作可能に構成された制御ロジック・ブロック（３０３）と、前記１対の前記乗算器の出力を加えるか減じるように動作可能に構成され、ＤＦＴ項の実数部または虚数部を得る加算器（４１０）と、を含む装置。
請求項6
先行する請求項の装置において、前記乗算器が２つの別個のバンク（４０３、４０６）内に配置される装置。
請求項7
先行する請求項の装置において、一定の係数のための乗算器が両方のバンク（４０３、４０６）内で複製される装置。
請求項8
請求項５〜７のいずれか１項の装置において、複数のＤＦＴ項を累算するように構成されたアキュムレータ（３０６、３０８）を含む装置。
請求項9
請求項５〜８のいずれか１項の装置において、前記乗算器が、符号・絶対値フォーマット、または符号無し整数フォーマットで動作する装置。
請求項10
請求項５〜９のいずれか１項の装置において、前記制御装置（３０３）によって活性化されない乗算器への入力が、定数値に強制される装置。
請求項11
ＧＮＳＳ受信器中の無線局地信号を処理するための信号プロセッサであって、請求項５〜１０のいずれか１項のＤＦＴを計算するための装置を含んでいる、装置。
請求項12
値を、一定の係数の有限集合の中の要素で乗ずるための方法であって、複数の乗算器ユニットを設けるステップであって、各乗算器ユニットは前記有限集合の中の一定の係数のうちの１つによって乗じるように具体的に構成されている、設けるステップと、前記値を、前記有限集合の中の所望の係数によって乗じる乗算器に選択的にルーティングするステップと、を具備する方法。
請求項13
先行する請求項の方法において、前記値および前記係数が複素数値を有する、方法。